Combinatorial optimization includes well known modelling problems such as the travelling salesman problem, real World problems such as scheduling problems and various pattern recognition problems (sometimes called constraint satisfaction problems). In particular, many common industrial resource allocation problems can be defined as combinatorial optimization problems. The task is usually to minimize cost given a number of constraints that describe the restrictions of the particular situation. In some cases the variables whose values are to be chosen are continuous (such as distance, weight, etc.), and then techniques such as linear programming are used. Often however, the entities to be determined are discrete, due to the fact that people and machines are indivisible, and cannot be assigned in fractions. Because of the combinatorial explosion, such problems are extremely difficult to solve optimally within a reasonable amount of time and they can often be proved to be NP-hard. For small problems exhaustive search may be possible, but for larger problems this is not possible. Certain problems may belong to a special case or allow for decomposition into smaller problems.
Examples of established methods are local optimization, selective combinatorial search, heuristics and integer linear programming. Hybrid methods are also sometimes used. Some methods, such as integer linear programming, emphasize the search for optimal solutions. Other methods, such as heuristics and probabilistic relaxation, try to find good but possibly suboptimal solutions. This is the most suitable approach for very large problems, since exact methods often fail to find a solution at all, while in practice it is often satisfactory to find suboptimal solutions.
Integer programming methods, which seem to be the most favored current approach, differ from intelligent search methods in the sense that they relax the integer constraints and instead work, with real valued, continuous variable. By doing so, linear programming techniques may be used to give continuous approximations to the combinatorial problem, from which integer solutions may sometimes be deduced. Examples of linear programming approaches can be found in U.S. Pat. Nos. 4,744,026, 4,744,027, 4,744,028, and 4,914,563.
Another possibility is to use the approach of neural or connectionist networks. There exists a wide variety of neural net architectures, although they all share some basic characteristics. The computation is distributed over a large number of nodes in a network, with each node working independently of the other nodes, only exchanging information with its neighbors in the network. The topology of the network may or may not reflect the specific problem to be solved. In some cases, the variables are allowed to vary continuously. In other networks, such as Boltzmann machines, the variables are discrete, and the network finds a solution by stochastically moving between different states guided by a method called simulated annealing.
The present invention is designed to provide a faster, more efficient approach to solving combinatorial optimization problems.